package com.guchenbo.example.dfs;

import lombok.Builder;
import lombok.Data;
import org.apache.commons.collections4.CollectionUtils;

import java.util.*;
import java.util.function.Function;

/**
 * @author guchenbo
 * @date 2024/8/21
 */
public class ViewNodeUtils {

    public static Map<String, List<String>> buildViewNodeMapAndSort(List<String> names,
                    Function<String, List<String>> dependcyFunction) {
        Map<String, ViewNodeUtils.ViewNode> viewNodeMap = buildViewNodeMap(names, dependcyFunction);
        Set<ViewNodeUtils.ViewNode> rootTrees = new LinkedHashSet<>();
        viewNodeMap.forEach((key, value) -> {
            if (value.isRoot()) {
                rootTrees.add(value);
            }
        });
        Map<String, List<String>> sortedTreeMap = new HashMap<>();
        rootTrees.forEach(view -> {
            List<String> vs = ViewNodeUtils.sortTree(view);
            sortedTreeMap.put(view.name, vs);
        });
        return sortedTreeMap;
    }

    private static Map<String, ViewNode> buildViewNodeMap(List<String> names,
                    Function<String, List<String>> dependcyFunction) {
        Map<String, ViewNode> viewNodeMap = new HashMap<>();

        Stack<String> stack = new Stack<>();
        names.forEach(stack::push);
        // 已经访问过的
        Set<String> pushed = new HashSet<>(names);

        while (!stack.isEmpty()) {
            String currentItem = stack.pop(); // 弹出栈顶元素
            ViewNode viewNode = buildViewNode(viewNodeMap, currentItem);

            // 每个元素只要计算一次依赖就可以了
            List<String> directDependencies = dependcyFunction.apply(currentItem);
            if (CollectionUtils.isNotEmpty(directDependencies)) {
                viewNode.setChildren(new ArrayList<>());
                for (String dependency : directDependencies) {
                    ViewNode childViewNode = buildViewNode(viewNodeMap, dependency);
                    childViewNode.setRoot(false);
                    viewNode.getChildren().add(childViewNode);

                    if (pushed.add(dependency)) { // 如果依赖没有被添加过
                        stack.push(dependency); // 将该依赖压入栈，处理它的依赖
                    }
                }
            }
        }
        return viewNodeMap;
    }

    private static List<String> sortTree(ViewNode root) {
        Set<String> sorted = new LinkedHashSet<>();
        Set<String> visited = new HashSet<>();
        Stack<ViewNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            ViewNode view = stack.peek();
            List<ViewNode> children = view.getChildren();
            if (children == null || children.isEmpty() || visited.contains(view.getName())) {
                stack.pop();
                sorted.add(view.getName());
                continue;
            }
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
            visited.add(view.getName());
        }
        return new ArrayList<>(sorted);
    }

    private static ViewNode buildViewNode(Map<String, ViewNode> viewNodeMap, String name) {
        return viewNodeMap.computeIfAbsent(name, k -> ViewNode.builder().name(k).root(true).build());
    }

    @Data
    @Builder
    public static class ViewNode {
        private boolean root;
        private String name;
        private List<ViewNode> children;
    }
}
